package splay;

/**
 * Laboratorio de Estrutura de Dados
 * @author talitalm - 20921059
 */

public class SplayTreeImpl implements SplayTree {

	private NoSplay root;

	public SplayTreeImpl() {
		this.root = new NoSplay();
	}

	private NoSplay rightRotate(NoSplay no) {
		
		NoSplay noAux = new NoSplay();
		noAux.setLeft(no.getLeft().getRight());
		noAux.setRight(no.getRight());
		noAux.setKey(no.getKey());

		no.setKey(no.getLeft().getKey());
		no.setLeft(no.getLeft().getLeft());
		no.setRight(noAux);

		return no;
		
/*		NoSplay parent = no.getParent();
		NoSplay aux = no.getRight();
		no.setParent(null);	// muda o pai de filho
		no.setRight(parent); // muda o filho Direito de filho
		parent.setParent(no); // muda o pai de pai
		parent.setLeft(aux); // muda o filho left de pai
		if (aux != null) // muda o pai do auxiliar
			aux.setParent(parent);
		
		root = no;
		return root;*/
		
	}

	private NoSplay leftRotate(NoSplay no) {
		NoSplay noAux = new NoSplay();

		noAux.setRight(no.getRight().getLeft());
		noAux.setLeft(no.getLeft());
		noAux.setKey(no.getKey());

		no.setKey(no.getRight().getKey());
		no.setRight(no.getRight().getRight());
		no.setLeft(noAux);

		return no;
	}

	private void splay(NoSplay no) {
		NoSplay avo = no.getParent().getParent();
		NoSplay pai = no.getParent();
		
		// CASO 1
		if (this.root.getKey() == pai.getKey()) { 
			if (this.root.getLeft().getKey() == no.getKey()) {
				rightRotate(pai); 
			} 
			
			else {
				leftRotate(pai); 
			}
		} 
		
		
		// CASO 2
		else if ((avo.getLeft().getKey() == pai.getKey())
				&& (pai.getLeft().getKey() == no.getKey())) { 
			rightRotate(avo); 
			
			rightRotate(pai);
		} 
		
		else if ((avo.getRight().getKey() == pai.getKey())
				&& (pai.getRight().getKey() == no.getKey())) {
			leftRotate(avo); 
			
			leftRotate(pai);
		} 
		
		
		// caso 3
		else { 
			if ((avo.getLeft().getKey() == pai.getKey())
					&& (pai.getRight().getKey() == no.getKey())) {
				leftRotate(pai); 
				
				rightRotate(avo);
			} else if ((avo.getRight().getKey() == pai.getKey())
					&& (pai.getLeft().getKey() == no.getKey())) {
				rightRotate(pai);
				leftRotate(avo);
			}
		}
	}

	@Override
	public int height() {
		
		int alturaLeft = -1;
		int alturaRight = -1;
		
		NoSplay temporario = this.root;
		while (!temporario.isEmpty()) {
			if (!temporario.getRight().isLeaf()) {
				temporario = temporario.getRight();
				alturaRight++;
			} else if (!temporario.getLeft().isEmpty()) {
				temporario = temporario.getLeft();
				alturaRight++;
			} else if (!temporario.getRight().isEmpty()) {
				temporario = temporario.getRight();
				alturaRight++;
			} else {
				break;
			}
		}
		
		
		temporario = this.root;
		
		while (!temporario.isEmpty() && !temporario.isLeaf()) {
			if (!temporario.getLeft().isLeaf()) {
				temporario = temporario.getLeft();
				alturaLeft++;
			} else if (!temporario.getRight().isEmpty()) {
				temporario = temporario.getRight();
				alturaLeft++;
			} else if (!temporario.getLeft().isEmpty()) {
				temporario = temporario.getRight();
				alturaLeft++;
			} else {
				break;
			}
		}
		
		
		
		return Math.max(alturaRight, alturaLeft);
	}

	public NoSplay search(int key) {

		NoSplay aux = root;
		while (true) {
			if (aux == null || aux.isEmpty()) {
				return aux;
			}
			if (key == aux.getKey()) {
				break;
			} else if (aux.getKey() < key) {
				aux = aux.getRight();
			} else if (aux.getKey() > key) {
				aux = aux.getLeft();
			}
		}
		return aux;
	}

	public void insert(int key) {

		NoSplay aux = root;

		while (!aux.isEmpty()) {
			if (aux.getKey() != key) {
				if (aux.getKey() < key) {
					aux = aux.getRight();
				} else if (aux.getKey() > key) {
					aux = aux.getLeft();
				}
			}
		}

		aux.setKey(key);
		aux.setLeft(new NoSplay());
		aux.setRight(new NoSplay());

	}

	public void delete(int key) {
		NoSplay aux = root;
		while (true) {
			if (aux == null || aux.isEmpty()) {
				return;
			}
			if (key == aux.getKey()) {
				if (aux.isLeaf()) {

					aux.setKey(-1);
					aux.setParent(new NoSplay());
				}

				else {
					aux.setKey(-1);
					root = aux.getLeft();
					root = aux.getRight();

				}
				break;
			} else if (aux.getKey() > key) {
				aux = aux.getLeft();
			} else if (aux.getKey() < key) {
				aux = aux.getRight();
			}
		}
	}

	@Override
	public String preOrder() {
		
		return stringPre(root);
	}

	private String stringPre(NoSplay no) {
		StringBuilder saida = new StringBuilder();
		if (!no.isEmpty()) {
			
			
			saida.append(stringPre(no.getLeft()));
			saida.append(stringPre(no.getRight()));
			saida.append(no.getKey() + " ");
		}
		return saida.toString();
	}

	@Override
	public int size() {
		if (root.isEmpty()) {
			return 0;
		}

		String tamanho = preOrder();
		String[] size = tamanho.split(" ");
		return size.length;
	}
}
